#include <stdio.h>

/* 
选择排序优化版：
在一趟遍历中，同时找出最大值和最小值，放到数组两端，这样就能将遍历的趟数减少一半
*/

void Swap(int *arr, int x, int y)
{
	int tmp = arr[x];
	arr[x] = arr[y];
	arr[y] = tmp;
}

void sel_sort(int *arr, int num)
{
	int left = 0;
	int right = num - 1;
	
	while(left < right)
	{
		int min = left;
		int max = right;
		int i  = 0;
		for(i  = left; i <= right; i++)
		{
			if(arr[i] < arr[min])
			{
				min = i;
			}
			if(arr[i] > arr[max])
			{
				max = i;
			}
		}
		// 最大值放在最右端
		Swap(arr, max, right);
		
		// 由于上一步把小标right 和 max上的数据进行了交换
		// 所以得考虑最小值arr[min] 在位置right的情况
		if( min == right)
		{
			min = max;
		}
		Swap(arr, min, left);
		
		printf("第%d轮排序：", left);
		for(i = 0; i < num; i++)
		{
			printf("%d ", arr[i]);
		}
		printf("\n");
		left++;
		right--;
	}
}

int main()
{
   /*  Write C code in this online editor and run it. */
    int i = 0;
	int arr[] = {3,5,9,2,4,7};
	int sz = sizeof(arr) / sizeof(arr[0]);
	
	printf("原始排序：");
	for(i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
	
	sel_sort(arr, sz);
	printf("最终排序：");
	for(i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
   
   return 0;
}